Méthodes de type off-policy avec approximations¶
3. Exemples de divergences¶
Nous allons maintenant nous intéresser à la deuxième problématique de l'apprentissage de type off-policy avec l'approximation de fonction, à savoir la distribution des mises à jour qui ne correspond pas à la distribution qu'on trouve dans le type on-policy. Nous allons voir sur quelques exemples que les méthodes semi-gradient peuvent conduire à des instabilités et des divergences
3.1. Un premier exemple de divergence¶
Problématique
Commençons par un premier exemple très simple. Considérons un fragment d'un MDP composé de deux états possédant des valeurs estimées sous la forme $w$ et $2w$, avec $\textbf w$ le poids qui dans notre exemple ne comprend qu'une composante $w$. Cela se produit dans le cadre de l'approximation des fonctions linéaires si les vecteurs caractéristiques des deux états sont de simples valeurs, ici $1$ et $2$. Sur le premier état, une seule action est disponible et on considère que la transition sur le second état est purement déterministe avec une récompense de $0$ (les informations dans les cercles correspondent aux valeurs des états):
Éude des mises à jour pendant l'entrainement
Supposons qu'à l'instant initial on ait $w=10$. La transition se fera alors depuis un état dont la valeur est estimée à 10 vers un état dont la valeur est estimée à 20. Cette condition sera considérée comme performante et la valeur de $w$ sera augmentée pour augmenter la valeur du premier état. Si le facteur de remise $\gamma=1$ alors la valeur de cette augmentation va dépendre de l'erreur TD(0) :
Ici la valeur du ratio d'échantillonnage est de $\rho = 1$ car il n'y a qu'une seule action à prendre et donc le ratio des probabilités entre la stratégie cible et la stratégie comportementale sera de $1$. L'algorithme semi-gradient va donc augmenter la valeur du poids $w$ de la valeur suivante (si par exemple $\alpha=0.1$).
La valeur du premier état prendra donc la valeur $w=11$ et la valeur du second état la valeur $2w=22$, soit une augmentation de $+1$ pour le premier état et de $+2$ pour le deuxième état.
Si une nouvelle transition apparaît, l'erreur TD(0) sera de ${\delta _{t+1}}=11$ et la valeur du poids sera de $w_{t+2}=12,1$. La valeur du premier état prendra donc la valeur $w=12,1$ et la valeur du second état la valeur $2w=24,2$. Cela correspond à une augmentation de $+1,1$ pour le premier état et de $+2,2$ pour le deuxième état. Il y a donc divergence vers l'infini.
Étude de la stabilité
On remarque que la mise à jour finale se fait en multipliant la dernière valeur du paramètre par ${1 + \alpha \left( {2\gamma - 1} \right)}$. Si cette constante est strictement supérieure à 1, alors le système va diverger et le paramètre $w$ va tendre vers l'infini (positivement ou négativement en fonction de sa valeur initiale). Dans le cas présent, la valeur du taux d'apprentissage $\alpha$ n'a aucun impact sur la stabilité, c'est la valeur du facteur de remise qui ne doit pas dépasser $\gamma \le 0.5$. La valeur du taux d'apprentissage ne jouera que sur la vitesse à laquelle le système va diverger.
Cette situation est plausible dans l'apprentissage off-policy
Dans cet exemple, l'unique transition se répète sans que la valeur de $w$ soit mise à jour à partir d'autres transitions. Cela est possible dans le cas de l'apprentissage off-policy car la stratégie comportementale peut sélectionner des actions que la stratégie cible ne prendrait jamais, ce qui induit une valeur de ratio d'échantillonnage préférentiel de $\rho = 0$ pour ces transitions. Dans ce cas, aucune mise à jour de serait réalisée.
Cette situation n'est pas plausible dans l'apprentissage on-policy
Dans l'apprentissage on-policy, la valeur du ratio d'échantillonnage est toujours de $\rho = 1$. Chaque fois qu'une transition d'un état $w$ vers un état $2w$ est réalisée et que la valeur de $w$ augmente, il y aura une transition en dehors de l'état $2w$. Cette nouvelle transition (ou les suivantes) réduira la valeur de $w$ et les valeurs s'équilibreront.
3.2. Exemple de Baird¶
Problématique
L'exemple vu précédemment n'est qu'un fragment d'un environnement et on peut se demander s'il existe réellement un MDP complet qui peut être instable. C'est le cas de l'exemple de divergence de Baird.
Considérons un environnement avec des tâches épisodiques de 7 états et à deux actions:
- Les actions en traits pointillés amènent l'agent de l'état n°7 vers un des six états du haut de manière équiprobable.
- Les actions en traits pleins amènent toutes l'agent vers l'état n°7.
Les stratégies utilisées sont les suivantes:
- La stratégie comportementale $b$ sélectionne les actions en traits pointillés avec une probabilité $b(a_1|⋅)=6/7$ et en traits plein avec une probabilité $\pi(a_0|⋅)=1/7$. La distribution de la probabilité de tomber sur un nouvel état suivant avec cette stratégie est donc uniforme.
- La stratégie cible $\pi$ sélectionne uniquement les actions en traits plein et donc avec une probabilité $\pi(a_0|\cdot)=1$
La récompense est nulle sur l'ensemble des transitions et le facteur de remise est de $\gamma=0.99$.
Les valeurs des états sont estimées avec une approximation linéaire de la forme indiquée dans les cercles. Par exemple, la valeur estimée de l'état n°1 est $V(1) = 2w_1+w_8$, où $w_1$ et $w_8$ sont les composantes du vecteur poids $\textbf w = (w_1,w_2,w_3,w_4,w_5,w_6,w_7,w_8)$. Cela correspondrait à un vecteur des caractéristiques $x(1)=(2,0,0,0,0,0,0,1)^T$.
Fonction de la valeur des états et valeur du vecteur poids attendue
La récompense étant nulle sur l'ensemble des transitions, la fonction des valeurs des états est $v_\pi(s)=0$, ce qui peut être approximé en prenant $\textbf w = 0$. En fait il existe plusieurs solutions car la dimension du vecteur poids est de 8 alors qu'il n'y a que 7 états et que les élément de l'ensemble des vecteurs caractéristiques $\left\{ {\textbf{x}(s):s \in S} \right\}$ sont linéairement indépendants :
Nous allons voir que l'application de l'algorithme semi-gradient TD(0) sur ce cas amène une divergence, et cela peu importe la valeur du taux d'apprentissage.